package MiddlePractice;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class Demo207 {
//	207. 课程表
//	你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
//
//	在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。
//
//	例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
//	请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
	
	//建图函数  输出List<Integer>[]
	private static List<Integer>[] createGraph(int numCourses, int[][] prerequisites){
		List<Integer>[] graph = new List[numCourses];
		for(int i = 0 ; i<numCourses; i++) {
			graph[i] = new LinkedList<>();
		}
		
		for(int i = 0 ; i<prerequisites.length; i++) {
			int to = prerequisites[i][0];
			int from = prerequisites[i][1];
			graph[from].add(to);
		}
		return graph;
	}
	
	private boolean hasCircle = false;
    private boolean[] path;
	private boolean[] visited;
	
	private boolean canFinish(int numCourses, int[][] prerequisites) {
		List<Integer>[] graph = createGraph(numCourses, prerequisites);
		visited = new boolean[numCourses];
		path = new boolean[numCourses];
		for(int i=0; i<numCourses; i++) {
			DFS(graph, i);
		}
		
		return !hasCircle;
    }
	
	private void DFS(List<Integer>[] graph, int vex) {
		if(path[vex]){
            hasCircle = true;
        }
        
        if(visited[vex] || hasCircle) {
			
			return;
		}
		
		visited[vex] = true;
        path[vex] = true;
		for(Integer neighbor : graph[vex]) {
			DFS(graph, neighbor);
		}
		
		//回溯前处理
		path[vex] = false;
	}
}
